package myself.a013Map;


import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @author 叶之越
 * Description
 * Date 2021/2/1
 * Time 14:58
 * Mail 739153436@qq.com
 */
public class Prim {
    // 最小生成树
    public static Set<Edge> primMST(Graph graph) {
        if (graph == null) {
            return new HashSet<>();
        }
        PriorityQueue<Edge> heap = new PriorityQueue<>((o1, o2) -> o1.weigth - o2.weigth);
        Set<Edge> edges = new HashSet<>();
        Set<Node> nodes = new HashSet<>();

        for (Node cur : graph.nodes.values()) {
            if (!nodes.contains(cur)) {
                nodes.add(cur);
                for (Edge edge : cur.edges) {
                    heap.add(edge);
                }
                while (!heap.isEmpty()) {
                    Edge edge = heap.poll();
                    Node next = edge.to;
                    if (!nodes.contains(next)) {
                        nodes.add(next);
                        edges.add(edge);
                        for (Edge nextEdge : next.edges) {
                            heap.add(nextEdge);
                        }
                    }
                }
            }
        }
        return edges;
    }
}
